package Top_Interview_Questions.Dynamic_Programming;

import java.util.Arrays;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/5 19:50
 * <p>
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/
 */
public class _0300 {

    public static void main(String[] args) {
        _0300 test = new _0300();
        int[] nums = {10,9,2,5,3,7,101,18};
        test.lengthOfLIS1(nums);
    }


    /**
     * 动态规划+二分法
     * tails[k] 的值代表 长度为 k+1 子序列 的尾部元素值
     * 设 res 为 tails 当前长度，代表直到当前的最长上升子序列长度
     *
     * 有点难理解
     */
    public int lengthOfLIS1(int[] nums) {
        int[] tails = new int[nums.length];
        int res = 0;
        for(int num : nums) {
            int i = 0, j = res;
            while(i < j) {
                int m = (i + j) / 2;
                if(tails[m] < num) i = m + 1;
                else j = m;
            }
            tails[i] = num;
            if(res == j) res++;
        }
        return res;
    }




    /**
     * 纯动态规划
     *  dp[i]的值代表以nums[i]结尾的最长子序列长度
     */
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

}
